package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    //leetcode 51 N皇后
    List<List<String>> ret;
    public boolean[] vis,vis1,vis2;
    public char[][] box;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        //vis用来记录同一列是否存在皇后
        vis = new boolean[n];
        //vis1用来记录正斜线上是否存在皇后
        vis1 = new boolean[2 * n];
        //vis2用来记录反斜线上是否存在皇后
        vis2 = new boolean[2 * n];
        box = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                box[i][j] = '.';
            }
        }
        backtracking(n,0);
        return ret;
    }

    public void backtracking(int n, int row) {
        if (row >= n) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(box[i][j]);
                }
                tmp.add(sb.toString());
            }
            ret.add(tmp);
        }
        for (int i = 0; i < n; i++) {
            if (!vis[i] && !vis1[row - i + n] && !vis2[row + i]) {
                box[row][i] = 'Q';
                vis[i] = true;
                vis1[row - i + n] = true;
                vis2[row + i] = true;
                backtracking(n, row + 1);
                box[row][i] = '.';
                vis[i] = false;
                vis1[row - i + n] = false;
                vis2[row + i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        test1.solveNQueens(4);
        System.out.println(333);
    }
}
